package com.singzi.leetcode.N100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class T0056 {
    public static void main(String[] args) {
        Solution0056 solution0056 = new Solution0056();
        int[][] k = {{1,3},{2,6},{7,7},{8,10},{15,18}};
        System.out.println(Arrays.deepToString(solution0056.merge(k)));
    }
}

class Solution0056 {
    public int[][] merge(int[][] intervals) {
        List<int[]> list = new ArrayList<>();
        int [] nums = new int[20000];
        int maxNum = 0;
        for (int[] interval : intervals) {
            for (int j = 2 * interval[0]; j <= 2 * interval[1]; j++) {
                if(interval[1] > maxNum) maxNum = interval[1];
                nums[j] = 1;
            }
        }
        boolean flag = true;
        int temp0 = 0;
//        System.out.println(maxNum);
        for (int i = 0; i <= 2*maxNum+1; i++) {
            if(flag&&nums[i] == 1) {
                temp0 = i/2;
                flag = false;
            }
            if(!flag&&nums[i]==0){
                int []temp = new int[2];
                temp[0] = temp0;
                temp[1] = (i-1)/2;
                list.add(temp);
                flag = true;
            }
        }
//        System.out.println(Arrays.toString(nums));
        int[][]num = new int[list.size()][2];
        return list.toArray(num);
    }
}


